import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
public class Demo7 {




     /* public long maximumTripletValue(int[] nums) {
            int left = 0;
            int mid = 1;
            int right = 2;
            long max = 0;
            while (!(right == mid+1 && mid == left+1 && right==nums.length)){
                  //先判断一下
                  long ret = (long)(nums[left]-nums[mid])*nums[right];
                  max = Math.max(max,ret);
                  //移动right，如果后边的比前面的大，就往后移动
                  while (right<nums.length-1 && nums[right]<nums[right+1]){
                        right++;
                  }
                  //再判断一下
                  ret = (long)(nums[left]-nums[mid])*nums[right];
                  max = Math.max(max,ret);

                  //移动mid和right
                  while (mid<right-1 && nums[mid]>nums[mid+1]){
                        mid++;
                  }
                  //再判断一下
                  ret = (long)(nums[left]-nums[mid])*nums[right];
                  max = Math.max(max,ret);

                  //移动left
                  while (left<mid-1 && nums[left]<nums[left+1]){
                        left++;
                  }
                  //再判断一下
                  ret = (long)(nums[left]-nums[mid])*nums[right];
                  max = Math.max(max,ret);

                  //判断一轮之后
                  if (right<nums.length){
                        right++;
                  }
                  if (mid<right-1){
                        mid++;
                  }
                  if (left<mid-1){
                        left++;
                  }
            }
            return max;

      }*/


/*      public long maximumTripletValue(int[] nums) {
            long max = 0;
            int n = nums.length;
            for(int i=0;i<n-2;i++){
                  for(int j = i+1;j<n-1;j++){
                        for(int k = j+1;k<n;k++){
                              long ret = (nums[i]-nums[j])*nums[k];
                              max = Math.max(max, ret);
                        }
                  }
            }
            return max;
      }*/





/*      public int maxSubarrays(int[] nums) {
            int count = 0;
            for(int i = 0;i<nums.length;i++){
                  if (nums[i] == 0){
                        count++;
                  }
            }
            if (nums[0] !=0 && nums[nums.length - 1]!=0){
                  return count+1;
            }
            if ((nums[0]==0 && nums[nums.length -1]!=0)
                        &&(nums[0]!=0 && nums[nums.length -1]==0){
                  return count;
            }
            if (nums[0]==0 && nums[nums.length -1]==0){
                  return count-1;
            }
      }*/


/*
      public int minOperations(int[] nums) {
            int[] hash = new int[1000001];
            for(int i = 0;i<nums.length;i++){
                  hash[nums[i]]++;
            }
            int count = 0;
            for(int i = 0;i<hash.length;i++){
                  if (hash[i]==1){
                        return -1;
                  }
                  if (hash[i] > 1){
                        if (hash[i]%3==0){
                              count += hash[i]/3;
                        }else if(hash[i]%3 == 1){
                              count += (hash[i]-4)/3+2;
                        }else{
                              count += hash[i]/3 + 1;
                        }
                  }
            }
            return count;


      }*/

/*
      public int minOperations(List<Integer> nums, int k) {
            List<Integer> list = new ArrayList<>();
            int count = 0;
            int ret = 0;
            int i = nums.size()-1;
            int[] hash = new int[k];
            while (count < k){
                  list.add(nums.get(i));
                  if (nums.get(i)<=k && nums.get(i)>0){
                        if (hash[nums.get(i)]==0){
                              hash[nums.get(i)] = 1;
                              count++;
                        }
                  }
                  ret++;
            }

            return ret;
      }
*/


/*      boolean[][] vis;
      int m,n;
      int step;
      int ret;
      int[] dx = {0,0,1,-1};
      int[] dy = {1,-1,0,0};
      public int uniquePathsIII(int[][] grid) {
            m =grid.length;
            n = grid[0].length;
            vis = new boolean[m][n];

            int bx = 0,by=0;
            for(int i = 0;i<m;i++){
                  for(int j = 0;j<n;j++){
                        if (grid[i][j] == 0){
                              step++;
                        }else if(grid[i][j]==1){
                              bx = i;
                              by = j;
                        }
                  }
            }
            step+=2;
            vis[bx][by] = true;
            dfs(grid,bx,by,1);
            return ret;

      }

      private void dfs(int[][] grid, int i, int j, int count) {
            if (grid[i][j] == 2){
                  if (count == step){
                        ret++;
                  }
                  return;
            }

            for(int k = 0;k<4;k++){
                  int x = i+dx[k];
                  int y = j+dy[k];
                  if (x>=0 && x<m && y>=0 && y<n && !vis[x][y] && grid[x][y] != -1){
                        vis[x][y] = true;
                        dfs(grid,x,y,count+1);
                        vis[x][y] = false;
                  }

            }



      }*/





/*      boolean[][] vis;
      int m,n;
      int[] dx = {0,0,1,-1};
      int[] dy = {-1,1,0,0};
      int ret = 0;
      public int getMaximumGold(int[][] g) {
            m = g.length;
            n = g[0].length;
            vis = new boolean[m][n];

            for(int i = 0;i<m;i++){
                  for(int j = 0;j<n;j++){
                        if (g[i][j] !=0){
                              vis[i][j] = true;
                              dfs(g,i,j,g[i][j]);
                              vis[i][j] = false;
                        }
                  }
            }

            return ret;

      }

      private void dfs(int[][] g, int i, int j, int path) {

            ret = Math.max(ret,path);

            for(int k = 0;k<4;k++){
                  int x = i+dx[k];
                  int y = j+dy[k];
                  if (x>=0 && x<m && y>=0 && y<n && !vis[x][y] && g[x][y]!=0){
                        vis[x][y] = true;
                        dfs(g,x,y,path+g[x][y]);
                        vis[x][y] = false;
                  }
            }


      }*/










/*
      boolean[][] vis;

      int m,n;

      char[] word;
      public boolean exist(char[][] board, String _word) {
            m = board.length;
            n = board[0].length;
            vis = new boolean[m][n];
            word = _word.toCharArray();
            for(int i = 0;i<m;i++){
                  for(int j = 0;j<n;j++){
                        if (board[i][j] == word[0]){
                              vis[i][j] = true;
                              if (dfs(board,i,j,1)){
                                    return true;
                              }
                              vis[i][j] = false;
                        }
                  }
            }
            return false;


      }

      int[] dx = {0,0,1,-1};
      int[] dy = {1,-1,0,0};
      private boolean dfs(char[][] board, int i, int j, int pos) {
            if (pos == word.length){
                  return true;
            }
            //上下左右匹配
            //利用向量数组，for循环
            for(int k=0;k<4;k++){
                  int x = i+dx[k];
                  int y = j+dy[k];
                  if (x>=0 && x<m && y>=0 && y<n && !vis[x][y] && board[x][y] == word[pos] ){
                        vis[x][y] = true;
                        if (dfs(board,x,y,pos+1)){
                              return true;
                        }
                        vis[x][y] = false;
                  }
            }
            return false;

      }*/














     /* boolean[][] row,col;
      boolean[][][] grid;


      public void solveSudoku(char[][] board) {
            row = new boolean[9][10];
            col = new boolean[9][10];
            grid = new boolean[3][3][10];

            for(int i = 0;i<9;i++){
                  for(int j = 0;j<9;j++){
                        if (board[i][j] != '.'){
                              int num = board[i][j] -'0';
                              row[i][num] = col[j][num]=grid[i/3][j/3][num]=true;

                        }
                  }
            }
            dfs(board);


      }

      private boolean dfs(char[][] board) {

            for(int i=0;i<9;i++){
                  for(int j = 0;j<9;j++){
                        if (board[i][j] == '.'){
                              //填数
                              for(int num = 1;num<=9;num++){
                                    if (!row[i][num] && !col[j][num] && !grid[i/3][j/3][num]){
                                          board[i][j] = (char)('0'+num);
                                          row[i][num] = col[j][num]=grid[i/3][j/3][num]=true;
                                          if (dfs(board) == true){
                                                return true;
                                          }
                                          //恢复现场
                                          board[i][j] = '.';
                                          row[i][num] = col[j][num]=grid[i/3][j/3][num]=false;
                                    }
                              }
                              return false;
                        }
                  }
            }
            return true;


      }

*/

   /*   boolean[][] row, col;
      boolean[][][] grid;
      public boolean isValidSudoku(char[][] board) {
            row = new boolean[9][10];
            col = new boolean[9][10];
            grid = new boolean[3][3][10];

            for(int i = 0;i<9;i++){
                  for(int j = 0;j<9;j++){
                        if (board[i][j] != '.'){
                              int num = board[i][j]-'0';
                              if (row[i][num] || col[j][num] || grid[i/3][j/3][num]){
                                    return false;
                              }
                              row[i][num] = true;
                              col[j][num] = true;
                              grid[i/3][j/3][num] = true;
                        }
                  }
            }
            return true;

      }*/













/*
      boolean[] checkCol,checkDig1, checkDig2;
      List<List<String>> ret;
      char[][] path;
      int n;
      public List<List<String>> solveNQueens(int _n) {
            n=_n;
            checkCol = new boolean[n];
            checkDig1 = new boolean[2*n];
            checkDig2 = new boolean[2*n];
            ret = new ArrayList<>();
            path = new char[n][n];

            for(int i = 0;i<n;i++){
                  Arrays.fill(path[i],'.');
            }
            dfs(0);
            return ret;


      }

      private void dfs(int row) {

            if (row==n){
                  //添加结果
                  List<String> tmp = new ArrayList<>();
                  for(int i = 0;i<n;i++){
                        tmp.add(new String(path[i]));
                  }
                  ret.add(new ArrayList<>(tmp));
            }

            for(int col=0;col<n;col++){
                  //判断能不能放
                  if (checkCol[col]==false && checkDig1[row-col+n]==false && checkDig2[row+col]==false){
                        path[row][col]='Q';
                        checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col]=true;
                        dfs(row+1);
                        //恢复现场
                        path[row][col]='.';
                        checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col]=false;


                  }

            }





      }*/












     /* List<List<String>> ret;
      List<String> path;
      //剪枝时的数组
      boolean[] col;
      boolean[] dig1;
      boolean[] dig2;
      public List<List<String>> solveNQueens(int n) {
            ret = new ArrayList<>();
            path = new ArrayList<>();
            col = new boolean[n];
            dig1 = new boolean[2*n];
            dig2 = new boolean[2*n];

            dfs(n,0);

            return ret;

      }

      private void dfs(int n, int pos) {
            if (pos == n){
                  ret.add(new ArrayList<>(path));
                  return;
            }

            //每一行的每个位置
            for(int x = 0;x<n;x++){
                  //遍历每一行时，依次尝试每一列的每一个位置
                  for(int y = 0;y<n;y++){
                        //先判断，再将皇后放到对应位置,更新布尔数组，再递归下一个，返回之后要剪枝
                        //判断是否是同一列
                        if (col[y]==true || dig1[y-x+n]==true || dig2[y+x]==true){
                              return;
                        }
                        //如果合法，就将皇后放到这个位置
                        //更改boolean数组
                        col[y] = true;
                        dig1[y-x+n]=true;
                        dig2[y+x]=true;
                        //在path中加入当前行
                        String str ="";
                        for(int i=0;i<n;i++){
                              if (i==y){
                                    str+='Q';
                              }
                              str+='.';
                        }
                        path.add(str);
                        dfs(n,y+1);
                        //剪枝
                        path.remove(path.size() - 1);

                  }
            }


      }
*/






/*      public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int m = in.nextInt();
//            int n = in.nextInt();
//            int count = 0;
//            int[][] array = new int[m][n];
//
//
//            for(int i = 0;i<m;i++){
//                  for(int j = 0;j<n;j++){
//                        //假设此位置可以放蛋糕
//                        array[i][j] = 1;
//                        for(int k = i;k>=0;k--){
//                              for(int l = j;l>=0;l--){
//                                    //遍历前边的数，如果放了蛋糕，那么就计算一下，看看这个位置能不能放
//                                    if (array[k][l]==1){
//                                          //计算是否能放蛋糕
//                                          int tmp = (i-k)*(i-k) + (j-l)*(j-l);
//                                          if (tmp==4){
//                                                //不能放蛋糕
//                                                array[i][j] = 0;
//                                                break;
//                                          }
//                                    }
//                                    if (j-l>2){
//                                          break;
//                                    }
//                              }
//                              if (array[i][j] == 0){
//                                    break;
//                              }
//                              if (i-k>2){
//                                    break;
//                              }
//                        }
//                        if (array[i][j] == 1){
//                              count++;
//                        }
//                  }
//            }
//            System.out.println(count);

//
//            char[] arr = {'1'};
//            int num = arr[0]-'0';
//            System.out.println(num);


            long a = Integer.MAX_VALUE + 1L;
            int b = (int)a;
            System.out.println(a);
            System.out.println(b);

      }*/











/*
      boolean[] check;
      int ret;

      public int countArrangement(int n) {
            check = new boolean[n+1];
            dfs(1,n);
            return ret;
      }

      private void dfs(int pos, int n) {
            if (pos == n+1){
                  ret++;
                  return;
            }

            for(int i = 1;i<=n;i++){
                  if (check[i] == false && ((i%pos == 0) || (pos%i)==0)){
                        check[i] = true;
                        dfs(pos+1,n);
                        check[i] = false;
                  }
            }

      }
*/








     /* StringBuilder path;
      List<String> list;
      public List<String> letterCasePermutation(String s) {
            list = new ArrayList<>();
            path = new StringBuilder();
            dfs(s,0);
            return list;
      }

      private void dfs(String s, int pos) {

            if (pos == s.length()){
                  list.add(path.toString());
                  return;
            }

            //不改变
            path.append(s.charAt(pos));
            dfs(s,pos+1);
            path.deleteCharAt(path.length() - 1);

            //改变
            if (s.charAt(pos ) <'0' || s.charAt(pos) > '9'){
                  char tmp = change(s.charAt(pos));
                  path.append(tmp);
                  dfs(s,pos+1);
                  path.deleteCharAt(path.length() - 1);
            }



      }

      public char change(char ch){
            if (ch>='a' && ch <= 'z'){
                  return ch-= 32;
            }else{
                  return ch+=32;
            }
      }
*/






/*      List<Integer> path;
      List<List<Integer>> ret;
      int aim;
      public List<List<Integer>> combinationSum(int[] nums, int target) {
            path = new ArrayList<>();
            ret = new ArrayList<>();
            aim = target;
            dfs(nums,0,0);
            return ret;

      }

      private void dfs(int[] nums, int pos, int sum) {
            if (sum==aim){
                  ret.add(new ArrayList<>(path));
                  return;
            }
            if (sum>aim || pos == nums.length){
                  return;
            }



      }*/



 /*     List<Integer> path;
      List<List<Integer>> ret;
      int aim;
      public List<List<Integer>> combinationSum(int[] nums, int target) {
            path = new ArrayList<>();
            ret = new ArrayList<>();
            aim = target;
            dfs(nums,0,0);
            return ret;

      }

      private void dfs(int[] nums, int pos, int sum) {
            if (sum==aim){
                  ret.add(new ArrayList<>(path));
                  return;
            }
            if (sum>aim || pos == nums.length){
                  return;
            }

            for(int i = pos;i<nums.length;i++){
                  path.add(nums[i] );
                  dfs(nums,i,sum+nums[i]);
                  path.remove(path.size() - 1);
            }


      }*/











/*

      int path;
      int aim;
      int ret;
      public int findTargetSumWays(int[] nums, int target) {
            aim = target;
            dfs(nums,0,0);
            return ret;
      }

      private void dfs(int[] nums, int pos,int path) {
            if (pos == nums.length){
                  if (path == aim){
                        ret++;
                  }
                  return;
            }


            dfs(nums,pos + 1,path+nums[pos]);

            dfs(nums,pos+1,path-nums[pos]);

      }



*/


/*      List<Integer> path;
      List<List<Integer>> ret;
      int n,k;
      public List<List<Integer>> combine(int _n, int _k) {
            n = _n;
            k=_k;
            path = new ArrayList<>();
            ret = new ArrayList<>();
            dfs(1);
            return ret;
      }

      private void dfs(int start) {
            if (path.size()==k){
                  ret.add(new ArrayList<>(path));
                  return;
            }

            for(int i=start;i<=n;i++){
                  path.add(i);
                  dfs(i+1);
                  path.remove(i);
            }

      }*/



















/*      int left,right,n;
      StringBuilder path;
      List<String> ret;

      public List<String> generateParenthesis(int _n) {
            n=_n;
            path = new StringBuilder();
            ret = new ArrayList<>();

            dfs();
            return ret;

      }

      private void dfs() {
            if (right == n){
                  ret.add(path.toString());
                  return;
            }

            if (left<n){
                  path.append('(');
                  left++;
                  dfs();
                  //回溯
                  path.deleteCharAt(path.length() - 1);
                  left--;
            }

            if (right<left){
                  path.append(')');
                  right++;
                  dfs();
                  path.deleteCharAt(path.length() - 1);
                  right--;
            }





      }*/



/*      String[] hash = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
      List<String> ret;
      StringBuilder path;
      public List<String> letterCombinations(String digits) {
            ret = new ArrayList<>();
            path = new StringBuilder();
            if (digits.length() == 0) return ret;

            dfs(digits,0);
            return ret;

      }

      private void dfs(String digits, int pos) {
            if (pos == digits.length()){
                  ret.add(path.toString());
                  return;
            }

            String cur = hash[digits.charAt(pos)-'0'];
            for(int i=0;i<cur.length();i++){
                  path.append(cur.charAt(i));
                  dfs(digits,pos+1);
                  path.deleteCharAt(path.length()-1);//恢复现场
            }

      }*/





/*    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        ListNode cur = head;
        while (list1 != null && list2!=null){
            if (list1.val<=list2.val){
                cur.next = list1;
                list1 = list1.next;
                cur = cur.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }
        while (list1 != null){
            cur.next = list1;
        }
        while (list2 != null){
            cur.next = list2;
        }
        return head.next;

    }*/



/*
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1==null){
            return list2;
        }
        if (list2==null){
            return list1;
        }

        if (list1.val<=list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }


    }
*/




/*
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }

    private void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {

        if (n==1){
            c.add(a.remove(a.size() - 1));
            return;
        }

        dfs(a,c,b,n-1);
        c.add(a.remove(a.size() - 1));
        dfs(b,a,c,n-1);


    }
*/


}
